public class code2 {

//    单链表排序
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        // write code here
        // 尝试将链表存储到数组中，之后进行排序后再重新构建
        int num = 0;
        ListNode p = head;
        while(p != null) {
            p = p.next;
            num++;
        }
        // 让 p 恢复到 head 节点处
        p = head;
        int[] arr = new int[num];
        int i = 0;

        while(p != null){
            arr[i] = p.val;
            p = p.next;
            i++;
        }

        // 通过 sort 实现一个降序排列
        Arrays.sort(arr);

        ListNode newNode = null;
        ListNode newhead = new ListNode(-1);
        ListNode p2 = newhead;

        for(int j= 0; j < num; j++) {
            newNode = new ListNode(arr[j]);
            p2.next = newNode;
            p2 = p2.next;
        }

        return newhead.next;
    }
}
